package algorithms

func Bsearch(arr []int, val int) int {
	high := len(arr) - 1
	low := 0
	for low <= high {
		mid := low + (high-low)>>1
		if arr[mid] == val {
			return mid
		} else if arr[mid] > val {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return -1
}

//变体一：查找第一个值等于给定值的元素
//实现一，向前遍历，麻烦
//func Bsearch1(arr []int,val int) int {
//	high := len(arr)-1
//	low := 0
//	for low <= high {
//		mid:=low+(high-low)>>1
//		if arr[mid]==val{
//			i:=mid-1
//			for i>=0{
//				if arr[i]!=val{
//					break
//				}else {
//					i--
//				}
//			}
//			i++
//			return i
//		}else if arr[mid]>val{
//			high=mid-1
//		}else {
//			low=mid+1
//		}
//	}
//	return -1
//}
//实现二，找到的时候比较一下前一个数字，如果相等则在前面的区间继续二分查找
func Bsearch1(arr []int, val int) int {
	high := len(arr) - 1
	low := 0
	for low <= high {
		mid := low + (high-low)>>1
		if arr[mid] > val {
			high = mid - 1
		} else if arr[mid] < val {
			low = mid + 1
		} else {
			if mid == 0 || arr[mid-1] != val {
				return mid
			} else {
				high = mid - 1
			}
		}
	}
	return -1
}

//变体二：查找最后一个值等于给定值的元素，和上一个相反
func Bsearch2(arr []int, val int) int {
	high := len(arr) - 1
	low := 0
	for low <= high {
		mid := low + (high-low)>>1
		if arr[mid] > val {
			high = mid - 1
		} else if arr[mid] < val {
			low = mid + 1
		} else {
			if mid == len(arr)-1 || arr[mid+1] != val {
				return mid
			} else {
				low = mid + 1
			}
		}
	}
	return -1
}

//变体三：查找第一个大于等于给定值的元素
func Bsearch3(arr []int, val int) int {
	high := len(arr) - 1
	low := 0
	for low <= high {
		mid := low + (high-low)>>1
		if arr[mid] >= val {
			if mid == 0 || arr[mid-1] < val {
				return mid
			} else {
				high = mid - 1
			}
		} else {
			low = mid + 1
		}
	}
	return -1
}

//变体四：查找最后一个小于等于给定值的元素
func Bsearch4(arr []int, val int) int {
	high := len(arr) - 1
	low := 0
	for low <= high {
		mid := low + (high-low)>>1
		if arr[mid] <= val {
			if mid == len(arr)-1 || arr[mid+1] > val {
				return mid
			} else {
				low = mid + 1
			}
		} else {
			high = mid - 1
		}
	}
	return -1
}

func searchRange(nums []int, target int) []int {
	i,j:=-1,-1
	high := len(nums) - 1
	low := 0
	for low <= high {
		mid := low + (high-low)>>1
		if nums[mid] > target {
			high = mid - 1
		} else if nums[mid] < target {
			low = mid + 1
		} else {
			if mid==0||nums[mid-1]!=nums[mid]{
				i=mid
				break
			}else {
				high=mid-1
			}
		}
	}
	high=len(nums) - 1
	for low<=high{
		mid := low + (high-low)>>1
		if nums[mid] > target {
			high = mid - 1
		} else {
			if mid==len(nums)-1||nums[mid+1]!=nums[mid]{
				j=mid
				break
			}else {
				low=mid+1
			}
		}
	}
	return []int{i,j}
}

func canJump(nums []int) bool {
	res:=false
	visited:=make([]bool,len(nums))
	var f func(int)
	f=func(i int){
		if res||visited[i]{
			return
		}
		visited[i]=true
		if i==len(nums)-1{
			res=true
			return
		}
		for tmp:=nums[i];tmp>0;tmp--{
			if i+tmp<len(nums){
				f(i+tmp)
			}
		}

	}
	f(0)
	return res
}
//69. x 的平方根
func mySqrt(x int) int {
	low,high:=0,x
	for low<=high{
		mid:=low+(high-low)>>1
		tmp:=mid*mid
		if tmp>x{
			high=mid-1
		}else if tmp<x{
			low=mid+1
		}else {
			return mid
		}
	}
	 if low*low>x{
	 	return low-1
	 }
	 return low
}

//33. 搜索旋转排序数组,二分查找变种
func search(nums []int, target int) int {
	low, high := 0, len(nums)-1
	if high < 0 {
		return -1
	}
	if high == 0 {
		if target == nums[0] {
			return 0
		}
		return -1
	}
	for low <= high {
		mid := low + (high-low)>>1
		if target == nums[mid] {
			return mid
		}
		//前半段有序，注意这里是等号，因为可能mid==low
		if nums[0] <= nums[mid] {
			if target < nums[mid] && nums[low] <= target {
				high = mid - 1
			} else {
				low = mid + 1
			}
		} else { //后半段有序
			if target > nums[mid] && nums[len(nums)-1] >= target {
				low = mid + 1
			} else {
				high = mid - 1
			}
		}
	}
	return -1
}
//240. 搜索二维矩阵 II,z字形查找
func searchMatrix(matrix [][]int, target int) bool {
	m,n:=len(matrix),len(matrix[0])
	i,j:=0,n-1
	for i<m&&j>=0{
		if matrix[i][j]>target{
			j--
		}else if matrix[i][j]<target{
			i++
		}else {
			return true
		}
	}
	return false
}
